package graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class AllPathsFromSourceToTarget797 {

    @Test
    public void test() {
        allPathsSourceTarget(new int[][]{new int[]{1}, new int[]{}});
        allPathsSourceTarget(new int[][]{new int[]{1,2}, new int[]{3}, new int[]{3}, new int[]{}});
        allPathsSourceTarget(new int[][]{new int[]{4,3,1}, new int[]{3,2,4}, new int[]{3}, new int[]{4}, new int[]{}});
        allPathsSourceTarget(new int[][]{new int[]{1,2,3}, new int[]{2}, new int[]{3}, new int[]{}});
    }

    // 找所有路径, 且是DAG, 就可以不用visited记录已访问过的了
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> path = new ArrayList<>(graph.length);
        traverse(0, graph, path, paths);
        System.out.format("count: %d, paths: %s\n", graph.length, paths);
        return paths;
    }

    public void traverse(int curr, int[][] graph, List<Integer> path, List<List<Integer>> paths) {
        // 可以把add放到最前面,if里面就不用再单独处理了,但是要记得remove()
        path.add(curr);
        if (curr == graph.length-1) {
            List<Integer> path0 = new ArrayList<>(path);
            paths.add(path0);
            path.remove(path.size()-1); // 这里不能忘了
            return;
        }
        //path.add(curr);
        for (int next: graph[curr]) {
            traverse(next, graph, path, paths);
        }
        path.remove(path.size()-1);
    }
}
